My Thoughts

I came across this fun puzzle on LeetCode. It forced me to think about palindromes in a deeper way than the typical stack data structure problems that palindromes are often linked to.

Check out the problem definition:

You are given a string s. You can convert s to a palindrome by adding characters in front of it.

Return the shortest palindrome you can find by performing this transformation.

Example 1:

Input: s = "aacecaaa"
Output: "aaacecaaa"

Example 2:

Input: s = "abcd"
Output: "dcbabcd"

Constraints:

0 <= s.length <= 5 * 104
s consists of lowercase English letters only.

My Solution

Given a string, s that is not a palindrome, the quickest possible way to turn s into a palindrome is by adding the last letter of s to the front of s. i.e. eep -> peep. Knowing this, the solution is easy. Simply tack on letters to the beginning of s, starting with the last letter of s and working your way to the front. The worst case scenario is that s requires all but its first letter to to be turned into a palindrome. i.e. asdf -> fdsasdf.

class Solution:

    def shortestPalindrome(self, s: str) -> str:
	# note: s[::-1] is the inverse of s
        if s == s[::-1]:
            return s
        reverse = s[::-1]
        total = reverse + s
        length = len(s)
        for i in range(length-1):
            output = reverse[0:(i+1)] + s
            if output == output[::-1]:
                return output